#include <iostream>
#include "Algo.h"

using namespace std;

const int MAX_VERTICES_NUMBER = 50;
const int MAX_EDGES_NUMBER = 70;
const int MAX_TEST_NO = 10;

inline vector<Edge> createRandomGraph(int verticesNumber) {
	set<Edge> edgesSet;
	int edgesNumber = rand() % MAX_EDGES_NUMBER;

	for (int i = 0; i < edgesNumber; ++i) {
		int vertexFrom = rand() % verticesNumber;
		int vertexTo = rand() % verticesNumber;
		edgesSet.insert(Edge(vertexFrom, vertexTo));
	}
	vector<Edge> edgesList(edgesSet.begin(), edgesSet.end());
	return edgesList;
}

inline vector<Edge> createFullGraph(int verticesNumber) {
	vector<Edge> result;
	for (int vertexFrom = 0; vertexFrom < verticesNumber; ++vertexFrom) {
		for (int vertexTo = 0; vertexTo < verticesNumber; ++vertexTo) {
			result.push_back(Edge(vertexFrom, vertexTo));
		}
	}
	return result;
}

inline vector<Edge> createAcyclicGraph(int verticesNumber) {
	vector<Edge> result;
	double probability = 0.1;
	for (int vertexFrom = 0; vertexFrom < verticesNumber; ++vertexFrom) {
		for (int vertexTo = vertexFrom + 1; vertexTo < verticesNumber; ++vertexTo) {
			double randomDouble = (rand() % 1000) / 1000;
			if (probability > randomDouble)
				result.push_back(Edge(vertexFrom, vertexTo));
		}
	}
	return result;
}

inline vector<Edge> createCyclicGraph(int verticesNumber) {
	vector<Edge> result;
	int curVertex = rand() % (verticesNumber - 1);
	int nextVertex = curVertex + 1;
	result.push_back(Edge(curVertex, nextVertex));
	vector<bool> visited(verticesNumber, false);
	visited[curVertex] = true;
	while (!visited[nextVertex]) {
		visited[nextVertex] = true;
		curVertex = nextVertex;
		nextVertex = rand() % verticesNumber;
		result.push_back(Edge(curVertex, nextVertex));
	}
	return result;
}

inline vector<Edge> createEmptyGraph(int verticesNumber) {
	vector<Edge> result;
	return result;
}

class TestingVisitor{
public:
	TestingVisitor(int verticesNumber) : entered_(verticesNumber, 0), leaved_(verticesNumber, 0) {}

	void comeToVertex(int vertex){
		entered_[vertex]++;
	}

	void processEdge(int vertexFrom, int vertexTo){}

	void leaveVertex(int vertex){
		leaved_[vertex]++;
	}

	bool allVisited(){
		for (size_t vertex = 0; vertex < entered_.size(); ++vertex) {
			if (entered_[vertex] != 1 || leaved_[vertex] == 0) {
				return false;
			}
		}
		return true;
	}

	bool equelVisitedLeaved(){
		for (size_t vertex = 0; vertex < entered_.size(); ++vertex) {
			if ((entered_[vertex] != leaved_[vertex]) || (entered_[vertex] >= 2)) {
				return false;
			}
		}
		return true;
	}

private :
	vector<int> entered_, leaved_;
};

inline void testDFS(const IGraph& graph) {
	try {
		TestingVisitor visitor(graph.getNumberOfVertices());
		DFS(graph, visitor);
		if (!visitor.allVisited()) {
			throw logic_error("FAIL");
			return;
		}
	}
	catch (const exception& ex) {
		throw logic_error("testDFS: " + string(ex.what()));
	}
}

inline void testBFS(const IGraph& graph) {
	try {
		TestingVisitor visitor(graph.getNumberOfVertices());
		BFS(graph, visitor, 0);
		if (!visitor.equelVisitedLeaved()) {
			throw logic_error("FAIL");
		return;
		}
	}
	catch (const exception& ex) {
		throw logic_error("testBFS: " + string(ex.what()));
	}
}

inline bool findCycle(const IGraph& graph, vector<bool>& visited, int processingVertex) {
	visited[processingVertex] = true;
	vector<int> incidenceList = graph.getIncidenceList(processingVertex);
	for (const auto incidentVertex : incidenceList) {
		if (visited[incidentVertex]) {
			return true;
		}
		else {
			findCycle(graph, visited, incidentVertex);
		}
	}
	return false;
}

inline bool hasCycle(const IGraph& graph) {
	int verticesNumber = graph.getNumberOfVertices();
	vector<bool> visited(verticesNumber);
	for (int vertex = 0; vertex < verticesNumber; ++vertex) {
		if (findCycle(graph, visited, vertex)) 
			return true;
	}
	return false;
}

inline void testTopologicalSort(const IGraph& graph) {
	try {
		int verticesNumber = graph.getNumberOfVertices();
		pair<bool, vector<int> > resultOfTopologicalSort = getTopologicalOrder(graph);
		bool success = resultOfTopologicalSort.first;
		vector<int> topologicalOrder = resultOfTopologicalSort.second;

		if (!success) {
			if (!hasCycle(graph)) throw logic_error("FAIL");
			return;
		}

		if ((int)topologicalOrder.size() != verticesNumber) 
			throw logic_error("FAIL");

		vector<int> positionInTopologicalOrder(verticesNumber);
		for (int index = 0; index < verticesNumber; ++index) {
			positionInTopologicalOrder[topologicalOrder[index]] = index;
		}

		for (int vertexFrom = 0; vertexFrom < verticesNumber; ++vertexFrom) {
			vector<int> incidenceList = graph.getIncidenceList(vertexFrom);
			for (const auto& vertexTo : incidenceList) {
				if (positionInTopologicalOrder[vertexFrom] > positionInTopologicalOrder[vertexTo])
					throw logic_error("FAIL");
			}
		}
	}
	catch (const exception& ex) {
		throw logic_error("testTopologicalSort: " + string(ex.what()));
	}
}

inline bool connectedByPath(const IGraph& graph, int vertexStart, int vertexFinish) {
	stack<int> verticesStack;
	verticesStack.push(vertexStart);
	vector<bool> visited(graph.getNumberOfVertices(), false);

	while (!verticesStack.empty()) {
		int processingVertex = verticesStack.top();
		if (processingVertex == vertexFinish)
			return true;
		verticesStack.pop();
		if (visited[processingVertex])
			continue;
		visited[processingVertex] = true;
		vector<int> incidenceList = graph.getIncidenceList(processingVertex);

		for (const auto& vertex : incidenceList) {
			if (!visited[vertex]) {
				verticesStack.push(vertex);
			}
		}
	}
	return false;
}

inline bool inOneComponent(const IGraph& graph, int firstVertex, int secondVertex) {
	return (connectedByPath(graph, firstVertex, secondVertex) && connectedByPath(graph, secondVertex, firstVertex));
}

inline void testTarjan(const IGraph& graph) {
	try {
		vector< set<int> > components = getComponents(graph);
		int verticesNumber = graph.getNumberOfVertices();
		vector<int> componentOfVertex(verticesNumber);
		for (size_t componentIndex = 0; componentIndex < components.size(); ++componentIndex) {
			for (const auto& vertex : components[componentIndex]) {
				componentOfVertex[vertex] = componentIndex;
			}
		}

		for (int firstVertex = 0; firstVertex < verticesNumber; ++firstVertex) {
			for (int secondVertex = 0; secondVertex < verticesNumber; ++secondVertex) {
				if ((componentOfVertex[firstVertex] == componentOfVertex[secondVertex] ? true : false) != inOneComponent(graph, firstVertex, secondVertex)) {
					throw logic_error("FAIL");
				}
			}
		}
	}
	catch (const exception& ex) {
		throw logic_error("TestTarjan: " + string(ex.what()));
	}
}

inline void testGetCondensationGraph(const IGraph& graph) {
	vector< set<int> > components = getComponents(graph);
	auto condensationGraph = getCondensationGraph(graph);
	if (condensationGraph->getNumberOfVertices() != components.size()) {
		throw logic_error("FAIL");
	}

	int verticesNumber = graph.getNumberOfVertices();
	vector<int> componentOfVertex(verticesNumber);
	for (size_t componentIndex = 0; componentIndex < components.size(); ++componentIndex) {
		for (const auto& vertex : components[componentIndex]) {
			componentOfVertex[vertex] = componentIndex;
		}
	}

	set<Edge> correctSetOfCondensationGraphEdges;
	for (int vertex = 0; vertex < verticesNumber; ++vertex) {
		vector<int> incidenceList = graph.getIncidenceList(vertex);
		for (size_t i = 0; i < incidenceList.size(); ++i) {
			if (vertex == incidenceList[i]) continue;
			if (componentOfVertex[incidenceList[i]] != componentOfVertex[vertex]) {
				correctSetOfCondensationGraphEdges.insert(Edge(componentOfVertex[vertex], componentOfVertex[incidenceList[i]]));
			}
		}
	}

	for (size_t vertexFrom = 0; vertexFrom < components.size(); ++vertexFrom) {
		vector<int> incidenceList = condensationGraph->getIncidenceList(vertexFrom);
		for (const auto& vertexTo : incidenceList) {
			if (correctSetOfCondensationGraphEdges.find(Edge(vertexFrom, vertexTo)) == correctSetOfCondensationGraphEdges.end()) {
				throw logic_error("FAIL");
			}
		}
	}
}

int getKthBit(int number, int k) {
	return (number >> k) % 2;
}

vector< unique_ptr<IGraph> > generateAllGraphsWithFixedVerticesNumber(int verticesNumber) {
	vector<Edge> allPossibleEdges;
	for (int vertexFrom = 0; vertexFrom < verticesNumber; ++vertexFrom) {
		for (int vertexTo = 0; vertexTo < verticesNumber; ++vertexTo) {
			allPossibleEdges.push_back(Edge(vertexFrom, vertexTo));
		}
	}

	int numberOfGraphs = 1;
	for (size_t i = 0; i < allPossibleEdges.size(); ++i) {
		numberOfGraphs *= 2;
	}

	vector<unique_ptr<IGraph> > result(numberOfGraphs);
	vector< vector<Edge> > edgesLists(numberOfGraphs);

	for (size_t edgeIndex = 0; edgeIndex < allPossibleEdges.size(); ++edgeIndex) {
		for (int graphIndex = 0; graphIndex < numberOfGraphs; ++graphIndex) {
			if (getKthBit(graphIndex, (int)allPossibleEdges.size()))
				edgesLists[graphIndex].push_back(allPossibleEdges[edgeIndex]);
		}
	}

	for (int graphIndex = 0; graphIndex < numberOfGraphs; ++graphIndex) {
		result[graphIndex] = makeCompactGraph(edgesLists[graphIndex], verticesNumber);
	}

	return result;
}

void testOnSmallGraphs() {
	for (int verticesNumber = 1; verticesNumber < 4; ++verticesNumber) {
		auto allGraphs = generateAllGraphsWithFixedVerticesNumber(verticesNumber);
		for (size_t graphIndex = 0; graphIndex < allGraphs.size(); ++graphIndex) {
			testTopologicalSort(*allGraphs[graphIndex]);
			testDFS(*allGraphs[graphIndex]);
			testBFS(*allGraphs[graphIndex]);
			testTarjan(*allGraphs[graphIndex]);
			testGetCondensationGraph(*allGraphs[graphIndex]);
		}
	}
	cout << "Test on small Graphs: OK" << "\n";
}

void testOnCyclicGraphs() {
	for (int testNo = 0; testNo < MAX_TEST_NO; ++testNo) {
		int verticesNumber = rand() % MAX_VERTICES_NUMBER + 2;
		vector<Edge> edgesList = createCyclicGraph(verticesNumber);
		auto graph = makeCompactGraph(edgesList, verticesNumber);
		testTopologicalSort(*graph);
		testDFS(*graph);
		testBFS(*graph);
		testTarjan(*graph);
		testGetCondensationGraph(*graph);
	}
	cout << "Test on cyclic graphs: OK\n";
}

void testOnAcyclicGraphs() {
	for (int testNo = 0; testNo < MAX_TEST_NO; ++testNo) {
		int verticesNumber = rand() % MAX_VERTICES_NUMBER + 2;
		vector<Edge> edgesList = createAcyclicGraph(verticesNumber);
		auto graph = makeCompactGraph(edgesList, verticesNumber);
		testTopologicalSort(*graph);
		testDFS(*graph);
		testBFS(*graph);
		testTarjan(*graph);
		testGetCondensationGraph(*graph);
	}
	cout << "Test on acyclic graphs: OK\n";
}

void testOnFullGraphs() {
	for (int testNo = 0; testNo < MAX_TEST_NO; ++testNo) {
		int verticesNumber = rand() % MAX_VERTICES_NUMBER + 2;
		vector<Edge> edgesList = createFullGraph(verticesNumber);
		auto graph = makeCompactGraph(edgesList, verticesNumber);
		testTopologicalSort(*graph);
		testDFS(*graph);
		testBFS(*graph);
		testTarjan(*graph);
		testGetCondensationGraph(*graph);
	}
	cout << "Test on full graphs: OK\n";
}

void testOnEmptyGraphs() {
	for (int testNo = 0; testNo < MAX_TEST_NO; ++testNo) {
		int verticesNumber = rand() % MAX_VERTICES_NUMBER + 2;
		vector<Edge> edgesList = createEmptyGraph(verticesNumber);
		auto graph = makeCompactGraph(edgesList, verticesNumber);
		testTopologicalSort(*graph);
		testDFS(*graph);
		testBFS(*graph);
		testTarjan(*graph);
		testGetCondensationGraph(*graph);
	}
	cout << "Test on empty graphs: OK\n";
}

void testOnRandomGraphs() {
	for (int testNo = 0; testNo < MAX_TEST_NO; ++testNo) {
		int verticesNumber = rand() % MAX_VERTICES_NUMBER + 2;
		vector<Edge> edgesList = createRandomGraph(verticesNumber);
		auto graph = makeCompactGraph(edgesList, verticesNumber);
		testTopologicalSort(*graph);
		testDFS(*graph);
		testBFS(*graph);
		testTarjan(*graph);
		testGetCondensationGraph(*graph);
	}
	cout << "Test on random graphs: OK\n";
}

void testAlgo() {
	testOnSmallGraphs();
	testOnFullGraphs();
	testOnEmptyGraphs();
	testOnCyclicGraphs();
	testOnAcyclicGraphs();
	testOnRandomGraphs();
}